The indicators for measuring the vulnerability of networks are abundant. This paper uses the Largest Connected Component (LCC) to evaluate the communication capability of the network currently, in other words, the robustness of networks. Furthermore, we use the number of components (the isolated nodes are excluded) and the scale of small components to evaluate the broken degree of the network. Then we can write down the definition of vulnerability indicators as follows: (i)

The scale of the LCC 1 Here we use S to represent the number of nodes in the LCC of the network. and represent node i and node j. is the edge between the node i and node j. The LCC is the carrier of the network traffic. Therefore, when the network is under attack, we can use the number of nodes in the LCC to evaluate the overall connected situation of the network. S is also an import indicator to indicate whether the network is failed.

Generally, the way to find out the critical nodes is to use node centrality algorithms. Different centrality indicators measure the nodes value from different angles. If we attack the network with different centrality algorithms, it will show different attack performances. Here we give some existing node centrality indicators. First, we introduce the degree centrality which is known as the most common used indicator.^[13] 4 Here i represents the node i in the network. Degree centrality indicates the value of the node by using the number of edges connected to it. Then the betweenness centrality^[28] which calculates the number of the shortest paths which pass the node is shown as 5 where is the number of the shortest paths from node s to node t passing node i. is the total number of the shortest paths from node s to node t. n is the total number of nodes. After that we introduce the closeness centrality which measures the distance of the node to other nodes in the network. The value of the closeness centrality^[11] shows the broadcasting time length of information in the network. 6 where represents the distance from node s to node t. Eigenvector centrality^[29] uses the eigenvectors of the adjacent matrix to indicate the importance of nodes 7 where A is the adjacent matrix. If there is an edge between node i and node j, we set . Otherwise, . Besides are eigenvalues of A, and the corresponding eigenvectors are . We also use Pagerank centrality^[30] to indicate the node’s value which is defined as 8 Here k(j) is the number of adjacent nodes of node j. q is the transition probability. What is more, the k-core centrality is an important indicator, which deletes the nodes of degree k and sets the centrality of the deleted nodes as k (k = 1,2,3, …). In this paper, we use to represent k-core centrality^[12] of the node i.

However, the existing centrality algorithms do not always perform well, especially under the limited attack capacity. Figure 1 shows the 20 most important nodes of different centrality algorithms in the Router network. From Fig. 1 we can find that different centrality algorithms select different important nodes, but there are also some nodes chosen by two or more algorithms. It is shown that the centrality algorithms measure the node importance from various aspects. However, the simulations will show the shortness of the existing centrality algorithms in the following part. In the percolation process of the network, we delete the nodes according to the order of the centrality. In simulations, we observed that the phase transition will not appear until at least 5 percents of the nodes are deleted. While deleting 5 percents of the nodes in the real networks may exceed the attack capacity. Furthermore, the nodes centrality just measure the importance of the single node, ignoring the linkage effect between nodes. Thus we need to design an algorithm which considers the connection between nodes and indicates the importance of the nodes as well.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. (color online) The visualization of nodes selected by different algorithms.

In order to show the different performances of the centrality algorithms, we do simulations on the real networks and the Barabasi Albert network with different assortativities. Table 1 and 2 give networks^[31–36] properties in our simulations.

Table 1.

Table 1.

Table 1. The real networks. . Networks n m C D Router 23441 32049 2.73 −0.18484 0.00152 123 1 0.000117 Yeast 2361 6646 5.63 −0.09910 0.13006 64 1 0.002386 Erdos 6927 11850 3.42 −0.11259 0.12390 507 1 0.000494 Powergrid 4941 6594 2.67 0.00347 0.08010 19 1 0.000540 Geom 9343 11898 2.55 0.24259 0.32024 102 0 0.000273 Polblogs 1490 16715 22.44 −0.22123 0.26265 351 0 0.015067 Roget 1022 3648 7.14 0.17912 0.14985 28 0 0.006992

Table 1. The real networks. .

Table 2.

Table 2.

Table 2. The artificial networks. . Networks n m C D BA1 1000 1996 3.992 −0.3 0.00802 55 2 0.003996 BA2 1000 1996 3.992 −0.1 0.01970 55 2 0.003996 BA3 1000 1996 3.992 0 0.01353 55 2 0.003996 BA4 1000 1996 3.992 0.1 0.01450 55 2 0.003996 BA5 1000 1996 3.992 0.3 0.01617 55 2 0.003996 BA6 1000 3984 7.968 −0.3 0.00028 131 4 0.007976 BA7 1000 3984 7.968 −0.1 0.04067 131 4 0.007976 BA8 1000 3984 7.968 0 0.03377 131 4 0.007976 BA9 1000 3984 7.968 0.1 0.03735 131 4 0.007976 BA10 1000 3984 7.968 0.3 0.11466 131 4 0.007976

Table 2. The artificial networks. .

Here n is the number of nodes in the network. m is the number of edges, is the mean degree, and is assortativity coefficient. C represents clustering coefficient. is the largest node degree and is the smallest node degree in the network. D measures the density of the network which is defined as 9 We can find that for sparse network, D is very small. The density of networks relative. If the network is fully connected (D = 1), our algorithm is disabled. However, at this time, it is useless to analyze the robustness of centrality. For most networks, D is small. These networks are sparse network.

We also compare performance in artificial network. BA networks are scale-free networks. Initially we have nodes fully connected. At each time step, we introduce a node with m edges, and the m edges are connected to other nodes with probability . After that we can use structural algorithm to change the assortativity of the network. Assortativity^[37] coefficient is defined as 10 where is the sum of degree and is the variance of degree. For structural algorithm, we randomly choose two links , at each time. If , we change the connections to , . Obviously in this algorithm, the degree distribution does not change. By repeating this process, we can get different networks with different .

In this paper, we tend to analyze the network using a new relation between nodes which is called as the dominated relation. For an undirected network , we use V to represent the vertex set and E to represent the edge set. To fully understand the dominated relation between nodes, we give definitions below.

In the 1-cut network, node a is one of the nodes whose degree is 1. Node b is connected with a. From the theories above, we can define node a is dominated by node b, in other words, there is a dominated relation between nodes a and b. We also define node b as the minimum cut of the network. Then we can merge the dominated nodes whose degree is one. This process can be repeated several times until there is no node whose degree is 1.

Then we focus on the situation when the network is 2-cut. In this situation we can say the nodes which connect only to the minimum cut are dominated by the minimum cut of the network. However, this relation is not reliable for deciding the critical vertex. In this paper we define a strongly dominated relation between nodes. Suppose one minimum cut of the network is (a,b), the dominated nodes of (a,b) are . We use , , to represent the profit of just deleting one node a, b or c. (The profit of nodes represents the degree of damage to the network) is the profit from deleting nodes a and b. If there is 11 Then we call (a,b) and have strongly dominated relation between them. Furthermore, we extend this strongly dominated relation to k-cut situation. Then we have 12 Here is the minimum cut set and are dominated nodes.

Using the strongly dominated relation between nodes, we can design dominated clustering algorithm (DCA) to find out the critical vertex. To find the important nodes is to find the nodes with high profit. In our algorithm, we merge nodes step by step, and use two lists to save the node information (value and size). Value is the profit of the node and size keeps the index of the other nodes merged by the node.

Generally, we suppose there are one-degree nodes in the network. So from the Lemma 1 we can gain the network is 1-cut. At the first step, we initially set the value of every node is 1, and the size of it just keep the index of itself. After that, we delete the dominated nodes and their values are added to the corresponding minimum cut nodes’ value. The value of the deleted nodes is set to be 0. According to Lemma 2, this process will be repeated until the network has no one-degree nodes.

Then we tend to deal with 2-cut situation. (a,b) are minimum cut and are dominated nodes. From formula (11), we obtain 13 Here we use v to represent value and s to represent the number of nodes in size. If the formula (11) is satisfied, we delete b and and set the value to zero. Then we connect node a to the nodes that node b used to be connected with. The value of a is set as the profit of (a,b). The profit is 14

During the process of dealing with 2-cut situation, the network may have new one degree nodes. We just deal with the nodes as the method of 1-cut. When the network is k-cut, we can extend our algorithm to k-cut. is minimum cut set and are dominated nodes. 15

At the merging step, we merge the k minimum cut nodes as 2-cut. The value is set as 16

Figure 2 shows several special cases for 1-cut, 2-cut, and 3-cut. We also show the merging method of each case.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. (color online) The node centrality of different algorithms.

Overall our algorithm is arranged as:

From formula (15), we can find that when k is larger the strongly dominated relation is harder to be satisfied. Generally, for real networks, when we deal with k-cut situation, k = 4 is enough. In this process, the information of the network is lossless, so we call this process as the lossless consolidation.

In Fig. 3, here is a small network with 52 nodes and 87 edges. In Step 1 of our algorithm, we find all the nodes with one degree, and then we merge the one-degree nodes into the connected nodes. At this moment, there exists no one-degree vertex in the network. In Step 2, firstly we find all the two-degree nodes. Then we focus on the nodes connected to these two-degree nodes and merge them into one node. For instance, we merge node A and the other nodes in the same circle into node A. Now we notice the existence of one-degree nodes in the network, so we repeat Step 1. Actually, Step 3 is the same as Step 1. At this point, we turn our attention to the cut point in the network. In Step 4, we find the one cut points, for instance, node C, and merge the other connected nodes into the one cut points, which is actually merge the nodes in the red circle into node C. In Step 5, two cut points are found and the nodes they connect are merged. For example, the nodes in the red circle are merged into node D. In this process, we should judge whether the nodes to be merged meet the combination condition before every merging.

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. (color online) The schematic diagram of mergence process.

The characteristics of our algorithm is that the algorithm focus on local structure of the network through cut nodes. We understand the network structures more clearly. The existing centralities can be divided into three classes which are neighborhood-based centralities, path-based centralities, and iterative refinement centralities. Neighborhood-based centralities are degree, k-core, H-index, and so on. These centralities focus on neighbor nodes of the central nodes. For path-based centralities, there are betweenness, closeness, and Subgraph centrality. These centralities concentrate on the shortest paths between nodes. For iterative refinement centralities, there are eigenvector, pagerank, HITs, and so on. These centralities are based on that the influence of a node is not only determined by the number of neighbor nodes, but also determined by the influence of its neighbor nodes. So in these centralities, every node gets support from its neighbor nodes. However, there is no centrality which concentrates on local dominated relations between nodes. In our algorithm, we calculate the node centrality using node mergence. This is also a characteristic of our algorithm.

After using the lossless consolidation, we can also do the lossy consolidation. This means the network will be further merged after applying our algorithm. The significance of the lossy consolidation is the visualization of the network. The real network has too many nodes to show the details of the network. Thus we want to merge the nodes first, and then the struct of the network will be easy to be shown. In lossy consolidation, firstly, we do community detection in the network after mergence. In every community, there are nodes which are connected with other nodes in other community. We call these nodes as gate nodes. In a community C, are nodes which are just connected with nodes in C. are gate nodes of the network. So the profit of is 17 In every community, we keep the gate nodes. For nodes , if there is , we keep the node . Otherwise, we delete it. Obviously, this process dose not satisfy the strongly dominated relation and the information of the network is missing, so we call this process as the lossy consolidation. The network after this process is easy for visualization.

To show the efficiency of our algorithm, we do simulation in the dataset. Figure 4(a) is the visualization of router network which has 23441 nodes. Figure 4(b) is the router network after mergence which has 1164 nodes. We can use the network with 1164 nodes and merge data to represent the whole network. It is easy to observe that figure 4(a) is too complicated to show the structure of the network, while figure 4(b) shows the details of the network.

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. (color online) Comparison of theoretical value and simulation value.

Table 3 shows the merging performance of different networks, and we can find that the dominated clustering algorithm can effectively merge the network. From lossless consolidation we can obtain strong dominated relation in the network. Then we use the node weight of the network after lossless consolidation to find out critical nodes.

Table 3.

Table 3.

Table 3. The merging performance of different networks. . Networks (size) Lossless Lossy Networks (size) Lossless Lossy Router (23441) 1164 1151 BA3 (1000) 282 211 Yeast (2362) 1091 1081 BA4 (1000) 278 241 Erdos (6927) 1774 429 BA5 (1000) 473 320 Powergrid (4941) 750 692 BA6 (1000) 638 5 geom (9343) 1299 1180 BA7 (1000) 1 1 polblogs (1490) 959 951 BA8 (1000) 401 150 Roget (1022) 804 745 BA9 (1000) 575 233 BA1 (1000) 252 7 BA10 (1000) 498 7 BA2 (1000) 11 8

Table 3. The merging performance of different networks. .

To verify the effectiveness of the algorithm, we utilize Spyder on the python platform to achieve the DCA algorithm we proposed. We compared the simulation results among different algorithms in different networks. In the simulation we used the Package networkx. We can use nx.degree(), nx.betweenness_centrality(), nx.pagerank(), nx.closeness_centrality(), nx.eigenvector_centrality(), and nx.k_core() to calculate six centralities. In order to guarantee the accuracy of the simulation results, we expand the scale of the networks and repeat the experiments to reduce the error. The simulation results are the average of the experimental data.

In this part, we tend to analyze the correlation between the dominated clustering algorithm and existing algorithms. Table 4 shows the top ten nodes obtained by our algorithm and their value and rank in other centrality algorithms. (In Table 4, the first item is value and the second item is rank). We can find that the nodes chosen by our algorithm rank different in other algorithms, which shows our algorithm measure the importance of the nodes in a new angle. From simulations later, we can prove that the important nodes in our algorithm are conducive to network attack under the limited capacity.

Table 4.

Table 4.

Table 4. The artificial networks. . Rank Degree Betweenness Closeness k-core Eigenvector Pagerank 1 63/37 0.0843/0 0.169/42 10/167 26514/58 0.00069/102 2 35/190 0.0563/11 0.169/42 10/167 14386/1050 0.00034/369 3 58/46 0.0535/61 0.147/670 10/167 19588/402 0.00083/54 4 55/53 0.0767/67 0.146/716 10/167 18106/470 0.00078/70 5 39/148 0.0279/126 0.145/876 4/1390 10972/1437 0.00054/188 6 36/176 0.0250/183 0.144/952 4/1390 10740/1444 0.00050/206 7 34/205 0.0205/187 0.144/952 7/875 11630/1200 0.00046/231 8 37/171 0.0324/70 0.094/19085 4/1390 16100/870 0.00064/129 9 14/1074 0.0317/83 0.094/19085 11/1 19838/365 0.00021/737 10 31/242 0.0117/25 0.155/431 3/2867 9622/1900 0.00045/243

Table 4. The artificial networks. .

Figure 5 shows comparison between dominated clustering algorithm and other centrality algorithms. Figure 5(a) measures the change of S during the process of deleting nodes. After deleting 0.18 percent of the nodes, dominated clustering algorithm performs best. S declines steadily. Figure 5(b) shows the change of C. We can find that dominated clustering algorithm generates more clusters than other algorithms. It means that the dominated clustering algorithm damages the network more thoroughly. Figure 5(b) is the change of M. The dominated clustering algorithm produces more clusters. The S of the dominated clustering algorithm is stable at 30 or so. We also use community detection algorithm (Greedy algorithm) to cluster nodes. Then we use the value of the nodes to show the importance of the nodes. From Fig. 5 we find that if we just use community detection algorithm, the performance of the attack is poor.

Fig. 5.

	Figure Option ViewDownloadNew Window
	Fig. 5. (color online) The comparison of algorithms in router network.

If we just attack the network using single indicator, this approach is too naive. There have been many existing researches describing this process as Information Maximum Problem (IMP). Given network G(V, E), the target is to find a set S to maximize function f(S). In this paper, f(S) represents the degree of damage to the network which is related with LCC. Here we use a heuristic algorithm.^[38] We obtain the remove nodes by adaptive recalculation, that is, to choose the node with the largest centrality at first, and then recalculate the centrality after removing the chosen node. Then we choose degree and betweenness to do this because of better performance. Greedy algorithm can also be used for choosing nodes. We choose top n nodes in every centralities as a strategy set. In every step of removing nodes, we choose the node which maximizes f(S).

In the Fig. 5(d), we find if we remove the nodes with recalculating betweenness, the attack performance can be better. This process costs so much time because of the calculate complexity of betweenness. However, our algorithm still performs best when the attack capacity is limited.

In this section, we pay more attention on the performances of the algorithms under real networks. Tables 5–7 show the LCC of the network after deleting 0.4%, 0.7%, 1% nodes respectively. Each table gives the LCC of the seven real networks after deleting certain percent nodes based on six centrality algorithms and DCA we proposed. The lighted number is the minimum of the row, in other words, the algorithm the lighted number corresponding to has the best performance under the certain situation. From three tables, it can be derived that DCA we proposed is more effective when the attacked nodes number is small, alternatively, the attack to the network has a limited capacity. When the attacked nodes number is allowed to be larger, the advantage of our algorithm becomes not so obvious. We also noticed that DCA has a better performance when the network is sparser.

Table 5.

Table 5.

Table 5. The performance in the real networks (q = 0.4%) . Network Betweenness Eigenvector Closeness Degree k-core Pagerank DCA Router (23441) 9998 18027 16225 12866 19129 14070 9762 Yeast (2362) 2151 2192 2165 2164 2207 2151 2128 Erdos (6927) 5625 6214 6186 5828 6384 5653 5587 Powergird (4941) 4914 4911 4826 4826 4917 4803 4425 Geom (7344) 3354 3426 3416 3410 3515 3340 3086 Polblogs (1490) 1184 1210 1209 1184 1216 1184 1168 Roget (1022) 1189 1212 1214 1196 1218 1189 1178

Table 5. The performance in the real networks (q = 0.4%) .

Table 6.

Table 6.

Table 6. The performance in the real networks (q = 0.7%). . Network Betweenness Eigenvector Closeness Degree k-core Pagerank DCA Router (23441) 4527 15687 14924 9064 17324 10176 8068 Yeast (2362) 2121 2172 2132 2118 2196 2107 2069 Erdos (6927) 4993 5785 5718 5163 6010 5052 4889 Powergird (4941) 4892 4857 4766 4766 4859 4706 4343 Geom (7344) 3168 3355 3289 3251 3459 3158 2870 Polblogs (1490) 1168 1205 1174 1174 1212 1174 1151 Roget (1022) 987 987 987 987 983 987 971

Table 6. The performance in the real networks (q = 0.7%). .

Table 7.

Table 7.

Table 7. The performance in the real networks (q = 1%). . Network Betweenness Eigenvector Closeness Degree k-core Pagerank DCA Router (23441) 2449 14611 14614 6067 15050 7901 7111 Yeast (2362) 2070 2158 2106 2075 2185 2065 2029 Erdos (6927) 4392 5433 5273 4666 5700 4433 4404 Powergird (4941) 4861 4852 4650 4650 4821 4592 3991 Geom (7344) 2976 3249 3168 3081 3322 2981 2686 Polblogs (1490) 1151 1200 1165 1164 1202 1160 1129 Roget (1022) 983 984 984 984 980 983 962

Table 7. The performance in the real networks (q = 1%). .

To show more detailed information about our algorithm, we display the results of deleting nodes from 0 to 1 in router networks in Fig. 6. We can find that when the attack capacity is not limited, the attack performance is similar for betweenness, degree, pagerank, and our algorithm. We can also find there is percolation phase in the process of deleting nodes. Furthermore, our algorithm focuses on the limited attack capacity. When the proportion of deleting nodes is below 1%, our algorithm is obviously better than other networks. In reality, it is impossible to have infinite attack capacity. For large networks, 1% of nodes may already have hundreds of nodes. So our algorithm is more practical.

Fig. 6.

	Figure Option ViewDownloadNew Window
	Fig. 6. (color online) The attack process of router network.

After that, we study the comparison between the attack performance of the dominated clustering algorithm (DCA) we proposed and that of other centrality algorithms. Different from the simulations before, this section focuses on the performance in the BA networks with different assortativity coefficients. To simplify the simulation and make the figures clearer, here, we choose the degree algorithm (DA) to represent the centrality algorithms because of its popularity and good performance.

The simulation results are shown in Fig. 7. The networks in this section are all BA networks with 1000 nodes. The networks in Figs. 7(a) and 7(b) have 4000 edges while the networks in Figs. 7(c) and 7(d) have 2000 edges. Figures 7(a) and 7(c) give the comparison under the networks more disassortative, while for Figs. 7(b) and 7(d), the networks are more assortative. Generally, figure 7 shows DCA performs better than DA when a few nodes are deleted. With the number of the deleted nodes increases, the performances of the two algorithms meet an intersection. Moreover, when the network is more assortative, the time they meet will be later, that is to say, the intersection will move right. That results further illustrate that the DCA we proposed is more useful for the network attack under the limited capacity and performance is better when the networks are more assortative.

Fig. 7.

	Figure Option ViewDownloadNew Window
	Fig. 7. (color online) The comparison of different performance in BA network. (a) Disassortative BA networks with 4000 edges, (b) assortative BA networks with 4000 edges, (c) disassortative BA networks with 2000 edges, (d) assortative BA networks with 2000 edges.